package demo.hw;

import java.util.ArrayList;
import java.util.List;

public class _分批萨 {
    public static void main(String[] args) {
        /**
         * 吃货和"馋嘴"两人到披萨店点了一份铁盘圆形披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的 服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
         * 由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从"吃货"开始，轮流取被萨。除了第一块破产可以任意选取外，其他都必须从缺口开始选
         * 他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货”知道"馋嘴"的想法。
         * 已知披萨小块的数量以及每块的大小，求”吃货”能分得的最大的披萨大小的总和。
         * 输入描述
         * 第 1行为一个正整数奇数 N，表示披萨小块数量.
         * 3≤N<500
         * 接下来的第 2 行到第 N + 1行(共 N 行)，每行为一个正整数，表示第i块披萨的大小
         * 1≤ i ≤N
         * 披萨小块从某一块开始，按照一个方向次序顺序编号为 1~N
         * 每块披萨的大小范围为[1,2147483647]
         *
         * 输出描述
         * "吃货”能分得到的最大的披萨大小的总和。
         * 示例1：
         * 输入
         * 5
         * 8
         * 2
         * 10
         * 5
         * 7
         * 输出
         * 19
         *
         * 说明
         * 此例子中，有 5 块披萨。每块大小依次为 8、2、10，5、7。
         * 按照如下顺序拿披萨，可以使”吃货"拿到最多披萨
         * "吃货”拿大小为 10 的披萨
         * "馋嘴”拿大小为 5 的披萨
         * "吃货"拿大小为 7的披萨
         * 馋嘴”拿大小为 8 的披萨
         * "吃货"拿大小为 2 的披萨
         * 至此，披萨瓜分完毕，"吃货"拿到的披萨总大小为 10 +7 + 2 = 19
         * 可能存在多种拿法，以上只是其中一种
         *
         * 核心逻辑：
         * 吃货回合：尝试左端和右端两种选择 需要回溯
         * 馋嘴回合：只选最大的 无需回溯，行为固定
         * 遍历所有第一块的选择，找到最大值
         */
        int[] pizza = {8, 2, 10, 5, 7};
        int maxSum = 0;

        // 吃货先吃任意一块
        for (int i = 0; i < pizza.length; i++) {
            List<Integer> remaining = new ArrayList<>();
            for (int j = 0; j < pizza.length; j++) {
                if (j != i) {
                    remaining.add(pizza[j]);
                }
            }
            int ret = play(remaining, pizza[i], false);
            if (ret > maxSum) maxSum = ret;
        }
        System.out.println(maxSum);
    }

    /**
     *
     * @param isEaterTurn 是否是吃货回合
     * @return
     */
    private static int play(List<Integer> remaining, int eaterSum, boolean isEaterTurn) {
        if (remaining.isEmpty()) {
            return eaterSum;
        }

        if (isEaterTurn) {// 当前是吃货回合
            // 吃货回合：尝试从左边或右边选择，返回最大值
            List<Integer> leftRemain = new ArrayList<>(remaining);
            int left = leftRemain.remove(0);
            int leftRet = play(leftRemain, eaterSum + left, false); // 下一回合是馋嘴

            List<Integer> rightRemain = new ArrayList<>(remaining);
            int right = rightRemain.remove(rightRemain.size() - 1);
            int rightRet = play(rightRemain, eaterSum + right, false); // 下一回合是馋嘴

            return Math.max(leftRet, rightRet);
        } else { // 当前是馋嘴的回合
            // 馋嘴回合：总是选择最大的那边
            List<Integer> newRemain = new ArrayList<>(remaining);

            if (newRemain.get(0) > newRemain.get(newRemain.size() - 1)) {
                newRemain.remove(0);
            } else {
                newRemain.remove(newRemain.size() - 1);
            }
            return play(newRemain, eaterSum, true); // 下一回合是吃货
        }
    }
}
